package com.lsa.shenn.common;

import java.util.List;

import com.lsa.helpers.IntArrayListAdapter;
import com.lsa.helpers.Utils;

public class InsertionSort implements Sorter
{
	public int[] sort(int[] array)
	{
		if (Utils.isEmpty(array))
			return array;

		sort(IntArrayListAdapter.adapt(array));

		return array;
	}

	public List<Integer> sort(List<Integer> array)
	{
		if (Utils.isEmpty(array))
			return array;

		int borderElementIdx = 1;
		
		while (borderElementIdx != array.size())
		{
			int borderElement = array.get(borderElementIdx);
			
			int i = borderElementIdx - 1;
			int dstIdx = -1;
			
			for (; i > -1; i--)
			{
				if (borderElement >= array.get(i))
				{
					break;
				}				
				else
				{
					dstIdx = i;
				}
			}
			
			if (dstIdx > -1)
			{
				Utils.moveElement(array, borderElementIdx, dstIdx);
			}
			
			borderElementIdx++;
		}

		return array;
	}
}
